Error correcting codes are a protection mechanism to ensure reliable transmission through noisy communication channels. The main principle of error correcting codes is to add redundancy to the information at the transmitter. This redundancy allows error detection and error correction at the receiver. Error correcting codes fall into one of several categories: block codes and tree codes. Block codes are memoryless codes whereas tree codes require memory (George C. Clark and J. Bibb Cain, Error-Correction Coding for Digital Communications, Plenum Press, 1981). There are several important block codes in use today such as Low Density Parity Check (LDPC), BCH, and Reed-Solomon codes. The most common tree codes are Convolutional codes. Block codes can be found in everyday products and services, where digital communication is used, like digital video, networks, hard disk drives, and satellites.
Block codes can be represented by two matrices (George C. Clark and J. Bibb Cain, Error-Correction Coding for Digital Communications, Plenum Press, 1981). One matrix defines the parity checks such that HcT=0 for a codeword (c) that is free of errors. This matrix is referred to as the parity check matrix (H). The other matrix is referred to as the Generator matrix (G). Together the generator matrix and the parity check matrix have the following relationship: (HGT=0). This relationship means that all codewords defined in (G) are valid codewords. Furthermore if an error occurs such that the received information is r=c+e. Then the error will generate a syndrome HrT=HcT+HeT=HeT which can be used to easily detect the error locations. In a systematic code, where c=[s p] and s contains the k information values and p contains the parity vector of n-k values. Then the Generator and parity check matrices are defined as G=[Ik P] and H=[−PT In-k], where P represents the parity check matrix, Ix represents the identity matrix of size (x by x).
The primary challenges with error correcting codes (ECC) is achieving near optimal use of available bandwidth and minimizing encoding and decoding complexity. ECCs that achieve near optimal use of available bandwidth are said to be near the Shannon limit. Unfortunately, these codes suffer from high decoding and encoding complexity. LDPC codes fall into this category of requiring high decoding and encoding complexity to achieve near Shannon limit performance (D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes,” Electronic Letters, Vol. 32, pp 1645-1646, August 1996).
Recently, the near Shannon limit LDPC codes have become important to Industry. They have found their way into consumer standards such as Digital Video Broadcasting (DVB), 10 Gigabit Ethernet over copper (10GBase-T), and high speed wireless (IEEE 802.11n). The main disadvantages to using LDPC codes in these standards are 1) implementing LDPC decoders requires a significant amount of power, area, and latency and 2) implementing efficient partially parallel encoders requires a significant amount of power and area (and/or storage) overhead. Therefore, efficient implementations of LDPC codes are important.
The present invention focuses on solving problem 2) from above. LDPC encoders can be implemented in several different ways depending on the specific LDPC code. In all cases the Generator (G) matrix multiplication method is valid. Due to the higher complexity of the LDPC decoder it is often more efficient to fold the matrix multiplication operation. Unfortunately, folding the matrix multiplication looses the advantage of the sparseness of the G matrix. The Richardson-Urbanke (RU) method (T. J Richardson and R. L. Urbanke, “Efficient Encoding of Low Density Parity Check Codes”, IEEE Transactions on Information Theory, Vol. 47 No. 2, February 2001) was proposed as an alternative encoder which takes advantage of the sparseness of the H matrix. Although the RU method achieves savings on implementation costs, it is primarily intended as a parallel design and suffers from high complexity when implemented in hardware. Designing partially parallel RU LDPC encoders is a challenging problem.
Low complexity block code encoders are important in minimizing the overall power consumption and area costs for digital transmitter systems. What is needed is a systematic method for designing partially parallel low complexity block code encoders (and circuits) that achieve minimal power consumption and area costs.